from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from math import ceil
from math import floor
from typing import List


class Solution:
    def circleGame(self, toys: List[List[int]], circles: List[List[int]], r: int) -> int:
        # 按x坐标排序所有的圆心位置
        circle_list = defaultdict(list)
        for x0, y0 in circles:
            circle_list[x0].append(y0)
        for x0, y_lst in circle_list.items():
            y_lst.sort()

        print(circle_list)

        ans = 0

        # 遍历每个玩具
        for x0, y0, r0 in toys:
            print("玩具:", x0, y0)

            # 两个圆心的最大距离（可取等于）
            distance = (r - r0)

            # 考虑所有可能的圆心的x坐标
            x_min = x0 - distance
            x_max = x0 + distance

            distance_square = pow(distance, 2)

            already_find = False

            for x1 in range(x_min, x_max + 1, 1):
                # 当前圆心的x坐标在y轴上的最远距离
                y_distance = pow(distance_square - pow((x0 - x1), 2), 0.5)

                # 考虑所有可能的圆心的y坐标
                y_min = ceil(y0 - y_distance)
                y_max = floor(y0 + y_distance)

                # 二分查找是否存在目标圆心位置
                idx1 = bisect_left(circle_list[x0], y_min)
                idx2 = bisect_right(circle_list[x0], y_max)

                print(x1, ":", [y_min, y_max], "->", circle_list[x0], idx1, idx2)

                if idx1 < idx2:
                    ans += 1
                    already_find = True
                    break

            if already_find:
                continue

        return ans


if __name__ == "__main__":
    print(Solution().circleGame(toys=[[3, 3, 1], [3, 2, 1]], circles=[[4, 3]], r=2))  # 1
    print(Solution().circleGame(toys=[[1, 3, 2], [4, 3, 1], [7, 1, 2]], circles=[[1, 0], [3, 3]], r=4))  # 2
